package com.mlh.dp.old;

/*在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。*/
public class MaximumSquare {
    public static void main(String[] args) {
        System.out.println('1' - '0');
    }

    //官方题解和我的思路一模一样
    //暴力递归
    //返回所在位置作为正方形的左上角能够达到的最大正方形边长（注意不是返回面积大小）
    //发现 所在位置作为正方形的左上角能够达到的最大正方形与周围方块的关系
    public static int method1(char[][] matrix, int row, int col) {
        if (matrix[row][col] == '0') {
            return 0;
        }
        if (row == matrix.length - 1 || col == matrix[0].length - 1) {
            return matrix[row][col] - '0';
        }
        //所在位置作为左上角能够形成的最大正方形取决于他左、右、右下能够形成最大正方形中  正方形边长最小的+1  前提是所在位置本身为1
        return Math.min(method1(matrix, row + 1, col + 1), Math.min(method1(matrix, row, col + 1), method1(matrix, row + 1, col))) + 1;
    }

    // 记忆搜索
    public static int method2(char[][] matrix, int row, int col, int[][] maxSquare) {
        if(maxSquare[row][col]!=-1){
            return maxSquare[row][col];
        }

        if (matrix[row][col] == '0') {
            maxSquare[row][col] = 0;
            return maxSquare[row][col];
        }
        if (row == matrix.length - 1 || col == matrix[0].length - 1) {
            maxSquare[row][col] = matrix[row][col] - '0';
            return maxSquare[row][col];
        }

        maxSquare[row][col] = Math.min(method1(matrix, row + 1, col + 1), Math.min(method1(matrix, row, col + 1), method1(matrix, row + 1, col))) + 1;
        return maxSquare[row][col];
    }

    //严格表依赖
    public static int method3(char[][] matrix){
        int row=matrix.length;
        int col=matrix[0].length;
        int max=0;
        int[][] maxSquare=new int[row][col];

        //maxSquare没必要初始化为-1
        //下面两个for循环可以浓缩成一个
        for(int i=0;i<maxSquare.length;i++){
            for(int j=0;j<maxSquare[0].length;j++){
                maxSquare[i][j]=-1;
                if (i == maxSquare.length - 1 || j == maxSquare[0].length - 1) {
                    maxSquare[i][j] = matrix[i][j] - '0';
                    max=Math.max(maxSquare[i][j],max);
                }
            }
        }
        for(int i=row-2;i>=0;i--){
            for(int j=col-2;j>=0;j--){
                if(matrix[i][j]=='0'){
                    maxSquare[i][j]=0;
                }else{
                    maxSquare[i][j]=Math.min(Math.min(maxSquare[i+1][j],maxSquare[i][j+1]),maxSquare[i+1][j+1])+1;
                    max=Math.max(maxSquare[i][j],max);
                }

            }
        }
        return max*max;//面积=边长*边长
    }
}

